/*************************************************************************
	> File Name: B_tree.cpp
	> Author: 
	> Mail: 
	> Created Time: Fri 16 Aug 2024 08:52:02 PM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define L(root, pos) (root->next[pos])
#define R(root, pos) (root->next[pos + 1])
#define LAST_KEY(root) (root->key[root->n - 1])
#define LAST_CHILD(root) (root->next[root->n - 1])
#define MAX_M 3
#define swap(a, b) { \
	__typeof(a) __c = a; \
	a = b; \
	b = __c; \
}
typedef struct Node {
	int n; // 关键字数量
	int key[MAX_M + 1]; // 关键字数组
	struct Node *next[MAX_M + 1]; // 边
} Node;

Node *getNewNode() {
	Node *p = (Node *)malloc(sizeof(Node));
	p->n = 0;
	memset(p->next, 0, sizeof(Node *) * (MAX_M + 1));
	return p;
}

Node *insertKey(Node *root, int key) {
	if(root == NULL) {
		root = getNewNode();
		root->key[(root->n)++] = key;
		return root;
	}
	int pos = 0;
	while (pos < root->n && root->key[pos] < key) pos += 1;
	if(root->key[pos] == key) return root;
	for(int i = root->n - 1; i >= pos; --i) {
		root->key[i + 1] = root->key[i];
 	}
	root->key[pos] = key;
	root->n += 1;
	return root;
}

Node *insertMaintain(Node *root, Node *child, int pos) {
	if(child->n < MAX_M) return root;
	int s_pos = MAX_M / 2;
	Node *node1 = getNewNode();
	Node *node2 = getNewNode();
	node1->n = s_pos;
	node2->n = MAX_M - 1 - s_pos;
	for(int i = 0; i < s_pos; i++) {
		node1->key[i] = child->key[i];
		node1->next[i] = child->next[i];
	}
	node1->next[s_pos] = child->next[s_pos];
	for(int i = 0; i < node2->n; i++) {
		node2->key[i] = child->key[i + s_pos + 1];
		node2->next[i] = child->next[i + s_pos + 1];
	}
	node2->next[node2->n] = child->next[child->n];
	for(int i = root->n; i >= pos; i--) {
		root->key[i + 1] = root->key[i];
		root->next[i + 1] = root->next[i];
	}
	root->key[pos] = child->key[s_pos];
	root->next[pos] = node1;
	root->next[pos + 1] = node2;
	root->n += 1;
	free(child);
	return root;
}

Node *__insert(Node *root, int key) {
	if(root == NULL || root->next[0] == NULL) {
		return insertKey(root, key);
	}
	int pos = 0;
	while(pos < root->n && root->key[pos] < key) pos += 1;
	if(pos < root->n && root->key[pos] == key) return root;
	__insert(root->next[pos], key);
	return insertMaintain(root, root->next[pos], pos);
}

Node *insert(Node *root, int key) {
	root = __insert(root, key);
	if(root->n == MAX_M) {
		Node *p = getNewNode();
		p->next[0] = root;
		root = insertMaintain(p, root, 0);
	}
	return root;
}

void eraseKey(Node *root, int pos) {
	for(int i = pos + 1; i < root->n; i++) {
		root->key[i - 1] = root->key[i];
	}
	root->n -= 1;
	return ;
}

void rightRotate(Node *root, int pos) {
	for(int i = R(root, pos)->n + 1; i >=0; --i) {
		R(root, pos)->key[i] = R(root, pos)->key[i - 1];
		R(root, pos)->next[i] = R(root, pos)->next[i - 1];
	}
	R(root, pos)->key[0] = root->key[pos];
	root->key[pos] = LAST_KEY(L(root, pos));
	R(root, pos)->next[0] = LAST_CHILD(L(root, pos));
	LAST_CHILD(L(root, pos)) =  NULL;
	R(root, pos)->n += 1;
	L(root, pos)->n -= 1;
	return ;
}

void leftRotate(Node *root, int pos) {
	L(root, pos)->key[L(root, pos)->n] = root->key[pos];
	L(root, pos)->n += 1;
	root->key[pos] = R(root, pos)->key[0];
	LAST_CHILD(L(root, pos)) = R(root, pos)->next[0];
	for(int i = 0; i < R(root, pos)->n; i++) {
		R(root, pos)->key[i] = R(root, pos)->key[i + 1];
		R(root, pos)->next[i] = R(root, pos)->next[i + 1];
	}
	LAST_CHILD(R(root, pos)) = NULL;
	R(root, pos)->n -= 1;
	return ;
}

void mergeNode(Node *root, int pos) {
	Node *node = getNewNode();
	for(int i = 0; i <= L(root, pos)->n; i++) {
		node->key[i] = L(root, pos)->key[i];
		node->next[i] = L(root, pos)->next[i];
	}
	node->n = L(root, pos)->n + 1;
    node->key[node->n - 1] = root->key[pos];
    for (int i = 0; i <= R(root, pos)->n; i++) {
        node->key[i + node->n]  = R(root, pos)->key[i];
        node->next[i + node->n] = R(root, pos)->next[i];
    }
    node->n += R(root, pos)->n;
    free(L(root, pos));
    free(R(root, pos));
    for (int i = pos + 1; i <= root->n; i++) {
        root->key[i - 1]  = root->key[i];
        root->next[i - 1] = root->next[i];
    }
    root->next[pos] = node;
    root->n -= 1;
    return ;
}

Node *eraseMaintain(Node *root, int pos) {
	int lower_bound = (MAX_M + 1) / 2 - 1;
	if(root->next[pos]->n >= lower_bound) return root;
	if(pos > 0 && root->next[pos - 1]->n > lower_bound) {
		rightRotate(root, pos - 1);
	} else if(pos < root->n && root->next[pos + 1]->n >lower_bound) {
		leftRotate(root, pos + 1);
	} else {
		if(pos > 0) mergeNode(root, pos - 1);
		else mergeNode(root, pos);
	}
	return root;
}

Node *__erase(Node *root, int key) {
	if(root == NULL) return root;
	int pos = 0;
	while(pos < root->n && root->key[pos] < key) pos += 1;
	if(root->next[0] == NULL) {
		if(root->key[pos] == key) eraseKey(root, pos);
		return root;
	} else {
		if(pos < root->n && root->key[pos] == key) {
			Node *temp = root->next[pos];
			while(temp->next[temp->n]) temp = temp->next[temp->n];
			// int val = temp->key[temp->n - 1];
			swap(root->key[pos], temp->key[temp->n - 1]);
		}
		root->next[pos] = __erase(root->next[pos], key);
	}
	return eraseMaintain(root, pos);
}

Node *erase(Node *root, int key) {
	root = __erase(root, key);
	if(root->n == 0) {
		Node *temp = root->next[0];
		free(root);
		root = temp;
	}
	return root;
}

void print_node(Node *root) {
	printf("%d : ", root->n);
	for(int i = 0; i < root->n; i++) {
		printf("%4d", root->key[i]);
	}
	printf(" | ");
	if(root->next[0] == NULL) goto output_end;
	for(int i = 0; i <= root->n; i++) {
		printf("%4d", root->next[i]->key[0]);
	}
output_end:
	printf("\n");
	return ;
}

void output(Node *root) {
	if(root == NULL) return ;
	print_node(root);
	for(int i = 0; i <= root->n; i++) {
		output(root->next[i]);
	}
	return ;
}

void clearRoot(Node *root) {
	if(root == NULL) return ;
	for(int i = 0; i<= root->n; i++) {
		clearRoot(root->next[i]);
	}
	free(root);
	return ;
}

int main() {
	srand(time(0));
	#define MAX_OP 15
	Node *root = NULL;
	for(int i = 0; i < MAX_OP; i++) {
		int val = rand() % 100;
		root = insert(root, val);
		printf("\ninsert %d to BTree.\n", val);
		output(root);
	}
	int x;
	while(~scanf("%d", &x)) {
		if(x == -1) break;
		root = erase(root, x);
		output(root);
	}
	clearRoot(root);
	return 0;
}
